package datastructure.unionfind;

/**
 *   并查集
 *
 * 547. 省份数量
 * 1202. 交换字符串中的元素
 * 684. 冗余连接
 * 947. 移除最多的同行或同列石头
 * 803. 打砖块
 * 721. 账户合并
 * 1319. 连通网络的操作次数
 *   双层拓扑
 *
 * 1203. 项目管理
 *   最小生成树
 *
 * 1584. 连接所有点的最小费用
 * 1489. 找到最小生成树里的关键边和伪关键边
 *
 *
 *
 *
 * 本题考察求并查集中单个连通分量的成环边条数
 */
public class 连通网络的操作次数_1319 {
    public int makeConnected(int n, int[][] connections) {
        if(n - 1 > connections.length ) return -1;
        //  1. 并查集  几个点成环  连线是多余的  即 两个点union时候发现root相等
        //  2. 求需要的连线数量  就是size数量 -1
        DSU dsu = new DSU(n);
        for(int[] connect : connections) {
            dsu.union2Points(connect[0], connect[1]);
        }
        return dsu.extraLink >= dsu.size - 1 ? dsu.size - 1 : -1;
    }

    private class DSU{
        // 记录节点的根
        private int[] root;
        // 连通分量大小
        private int size;
        // 多余的连线
        private int extraLink;


        public DSU(int n){
            root = new int[n];
            for(int i = 0; i<n;) {
                root[i] = i++;
            }
            size = n;
            extraLink = 0;
        }

        public void union2Points(int x, int y){
            int xRoot = findRoot(x);
            int yRoot = findRoot(y);
            if(xRoot != yRoot) {
                root[yRoot] = xRoot;
                findRoot(y);
                // 合并两个点 孤岛减一
                size --;
            } else {
                // 根相同  表示成环了  连线多余
                extraLink ++;
            }
        }

        private int findRoot(int x) {
            return root[x] == x ? x : findRoot(root[x]);
        }
    }


    public static void main(String[] args) {
        连通网络的操作次数_1319 a = new 连通网络的操作次数_1319();
        int i = a.makeConnected(5, new int[][]{{0, 1}, {0, 2}, {3, 4}, {2, 3}});
        System.out.println();
    }
}
